Wireless mesh networks (WMNs) are multi-hop infrastructure-less networks characterized by dynamic self-organization, self-configuration and self-healing. These factors allow WMNs to support fast, reliable and cost-effective network deployment in very diverse environments, and provide better coverage and capacity to stationary and mobile users. Correspondingly, WMNs can host a wide range of applications in disaster recovery, commercial and private settings. One typical example is the Ericsson Response program, which uses WMN infrastructure to enhance robustness and quick deployment of transportable cellular networks, and provide effective and robust services in disaster rescue and other mission-critical scenarios.
In wireless mesh networks in particular, and in other networks, it is desirable for each network node to be able to determine to which nodes it has direct links; those are its neighbours. Existing neighbour detection schemes are based on a soft-state mechanism by exchanging periodical heartbeat (i.e. HELLO) messages, such as are described “Mobile Ad hoc Networking (MANET) Neighbourhood Discovery Protocol (NHDP)—draft-ietf-manet-nhdp-07”, Clausen et al, Internet Engineering Task Force, available at http://tools.ietf.org/html/draft-ietf-manet-nhdp-07. Each node in wireless mesh networks generates periodic HELLO messages for each of its interfaces. Each HELLO message identifies that interface, and reports the other interfaces of the node. Each HELLO message contains information from the link repository of the interface information base of the interface, and from the node repository of the node.
HELLO messages are sent proactively at a regular interval, known as HELLO_INTERVAL. The interval can be fixed or dynamic. For example, the interval can be backed off in order to reduce network congestion caused by control traffic. HELLO messages can also be sent in a reactive way, as a response to a change in the node itself or its neighbours.
If the HELLO messages from the neighbours are not received within a specific interval (known as Neighbour_Expiration_Interval), the node would assume its neighbour unreachable.
Due to the simplicity and robustness, most of existing routing protocols such as Optimised Link State Routing Protocol (OLSR) and Ad Hoc on Demand Distance Vector (AODV) routing use this neighbour detection scheme.
If link layer information describing connectivity to neighbouring nodes is available (i.e., loss of connectivity such as through absence of a link layer acknowledgment), this information can be used in addition to the information from the HELLO-messages to maintain the neighbour status.
For example, failure to transmit a packet after the maximum number of retransmission attempts in IEEE 802.11 results in an indicator signifying a failed transmission. This indicates the loss of the link to the active next hop. Upon receiving such a notification, the node removes the neighbouring nodes from its neighbour repository.
In addition to HELLO messages, an Ad Hoc on Demand Distance Vector (AODV) [4] node determines neighbour status by passively listening for packets from its neighbours. If a valid route to a neighbour exists but no data packets from that neighbour have been received for more than (ALLOWED_HELLO_LOSS*HELLO_INTERVAL) milliseconds, the node assumes that the link to this neighbour is currently lost.
The major concern about the HELLO based neighbour detection scheme is the detection latency. The node has to wait until the neighbour state timer expires before it senses the neighbour changes. In typical implementations this timeout is in the region of around 6 seconds. Such latency is usually not acceptable.
Another concern raised very recently is that the size of the Hello messages might be too large. Since bandwidth is scarce in wireless networks, periodic messages should be small.
Notifications from the link layer might lead to false neighbour removal. In addition to link breakage or neighbour loss, link-layer notification can be triggered by some other reasons, such as channel congestion. A link might be falsely removed when the channel to a neighbouring node is congested.
Passively Monitoring Data Flows is clearly not applicable when there is no data transmission in the nodes or the network. Otherwise, the neighbour repository of the nodes would slowly “churn” as neighbours are discovered and then timeout if there is no data traffic is transmitted.